package 实现数据结构.算法.栈;


import java.util.Stack;

/**
 * 栈： 先进后出
 * Stack<Character> t = new Stack<Character>();
 * t.push('a');
 * t.push('b');
 * t.peek(); // 这里得到栈顶元素'b'
 * t.pop();  // 这里将栈顶元素'b'弹出
 * t.peek(); // 此时栈顶元素为'a'
 * t.pop();  // 这里将栈顶元素'a'弹出
 */
public class _栈_括号匹配问题 {
    public static void main(String[] args) {
//        String s1 = "()()";
//        String s2 = "()())))";
//        /** 广度扩展 */
//        System.out.println(isValid(s1));
//        System.out.println(isValid(s2));
//
//        /** 广度扩展 */
//        System.out.println(isValid2(s1));
//        System.out.println(isValid2(s2));
//
//        String str1 = "()[]{}";
//        String str2 = "]][]{}";
//        /** 广度扩展 */
//        System.out.println(isValid3(str1));
//        System.out.println(isValid3(str2));

        // 初始 鱼大小 和鱼游动方向；
        int[] fish = {4, 3, 2, 1, 5}, dir = {0, 1, 0, 0, 0};
        System.out.println(solution(fish,dir)); // 2
        int[] fish2 = {4, 2, 5, 3, 1}, dir2 = {1, 1, 0, 0, 0};
        System.out.println(solution(fish2,dir2)); // 3


    }


    /**
     * 例 1：判断字符串括号是否合法
     * 【题目】字符串中只有字符'('和')'。合法字符串需要括号可以配对。比如：
     * <p>
     * 输入："()"
     * <p>
     * 输出：true
     * <p>
     * 解释：()，()()，(())是合法的。)(，()(，(()是非法的。
     * <p>
     * 请你实现一个函数，来判断给定的字符串是否合法。
     * <p>
     * 复制代码
     * boolean isValid(String s);
     * <p>
     * 每个字符只入栈一次，出栈一次，所以时间复杂度为 O(N)，而空间复杂度为 O(N)，
     * 因为最差情况下可能会把整个字符串都入栈。
     */
    public static boolean isValid(String s) {
        // 1. 先考虑边界问题
        if (null == s || s.length() == 0) {
            return true;
        }
        if (s.length() % 2 == 1) {
            return false;
        }
        // 2. 将（ 压栈，遇到 ） 弹出 看最终栈是否为空
        Stack stack = new Stack();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(c);
            } else if (c == ')') {
                // 如果栈此时为空了，遇到右括号就没必要判断了，直接返回false
                if (stack.isEmpty()) {
                    return false;
                }
                stack.pop();
            }
        }
        return stack.isEmpty(); // 0 true
    }


    /**
     * 例2：
     * 每个字符只入栈一次，出栈一次，所以时间复杂度为 O(N)，而空间复杂度为 O(1)
     */
    public static boolean isValid2(String s) {
        // 1. 先考虑边界问题
        if (null == s || s.length() == 0) {
            return true;
        }
        if (s.length() % 2 == 1) {
            return false;
        }
        // 2. 栈中元素都相同时，实际上没有必要使用栈，只需要记录栈中元素个数
        int leftNum = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                leftNum++;
            } else if (c == ')') {
                // 如果遇到右括号此时leftNum 已经为0或者负数了，直接返回false
                if (leftNum <= 0) {
                    return false;
                }
                leftNum--;
            }
        }
        return leftNum == 0; // 0 true
    }


    /**
     * 例3： 广度扩展
     * 【题目扩展】给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。有效字符串需满足：
     * 左括号必须用相同类型的右括号闭合
     * 左括号必须以正确的顺序闭合
     * <p>
     * 注意空字符串可被认为是有效字符串
     * <p>
     * 请实现接口： public boolean isValid(String s)
     * <p>
     * 结题：
     * 1、边界条件 空字符串 null 均为true, 但是基数的长度不符 返回false
     * 2、当遇到左括号直接压栈
     * 3、当遇到右括号并且当前栈为空或者栈顶元素不能和当前元素组成一对的时候返回false,否则弹出栈顶元素即可。
     * <p>
     * https://leetcode-cn.com/problems/valid-parentheses/
     */
    public static boolean isValid3(String s) {
        // 1. 定义边界条件
        if (null == s || s.length() == 0) {
            return true;
        }
        if (s.length() % 2 == 1) {
            return false;
        }
        // 2. 定义栈（存放不同元素）
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else if (c == ')') {
                if (stack.isEmpty() || stack.peek() != '(') {
                    return false;
                }
                stack.pop();
            } else if (c == ']') {
                if (stack.isEmpty() || stack.peek() != '[') {
                    return false;
                }
                stack.pop();
            } else if (c == '}') {
                if (stack.isEmpty() || stack.peek() != '{') {
                    return false;
                }
                stack.pop();
            } else {
                return false;
            }
        }

        return stack.empty();
    }

    /**
     * 例 4：大鱼吃小鱼问题
     * 【题目】在水中有许多鱼，可以认为这些鱼停放在 x 轴上。再给定两个数组 Size，Dir，Size[i] 表示第 i 条鱼的大小，Dir[i] 表示鱼的方向 （0 表示向左游，1 表示向右游）。这两个数组分别表示鱼的大小和游动的方向，并且两个数组的长度相等。鱼的行为符合以下几个条件:
     * <p>
     * 所有的鱼都同时开始游动，每次按照鱼的方向，都游动一个单位距离；
     * <p>
     * 当方向相对时，大鱼会吃掉小鱼；
     * <p>
     * 鱼的大小都不一样。
     * <p>
     * 输入：Size = [4, 2, 5, 3, 1], Dir = [1, 1, 0, 0, 0]
     * <p>
     * 输出：3 (还剩下三条鱼)
     * 注意：当鱼的游动方向相同，或者相反时，并不会相遇，此时大鱼不能吃掉小鱼。
     * <p>
     * <p>
     * 解题：同方向的鱼依次入栈，当有新的鱼进来后与之栈顶鱼比较，同方向的入栈，相向的则比较大小，如栈顶元素比较小则弹出 知道没有比他小的，然后再入栈
     */
    public static int solution(int[] fish, int[] dir) {
        // 1. 定义边界问题
        int fishNum = fish.length;
        if (fishNum <= 1) {
            return fishNum;
        }
        // 定义鱼游动方向
        int left = 0, right = 1;
        // 定义栈模型
        Stack<Integer> stack = new Stack();
        // 遍历鱼
        for (int i = 0; i < fish.length; i++) {
            // 当前鱼游动的情况
            int curFish = fish[i];
            int curFishDir = dir[i];
            // 当前鱼是否被栈中的鱼吃调
            boolean hasEat = false;
            // 如果栈中还有鱼，并且栈中鱼向右，当前的鱼向左游，那么就会有相遇的可能性
            while (!stack.isEmpty() && dir[stack.peek()] == right && curFishDir == left) {
                if (fish[stack.peek()] > curFish) {
                    hasEat = true;
                    break;
                }
                // 如果栈中的鱼较小，那么会把栈中的鱼吃掉，栈中的鱼被消除，所以需要弹栈。
                stack.pop();

            }
            // 如果新来的鱼 没有被吃掉 则入栈
            if (!hasEat) {
                stack.push(i);
            }
        }
        return stack.size();
    }

}



